Equal Sum Subarrays
Let's solve the Equal Sum Subrrays problem using Dynamic Programming.
Statement#
For a given array nums, determine if the array can be divided into two subarrays such that the sum of both the subarrays is equal.
For example, we have an array
The total length of this array can be denoted as
that is . An array can only be divided into two equal subarrays if the total sum of the array is even. In this case, the total sum of array elements is
, so two equal sum subarrays can be obtained here, as and , both having an equal sum of . In this case, TRUE will be returned as the array can be divided into two equal sum subarrays.
In case, the sum of array elements is odd or the array can not be divided into two equal sum subarrays, FALSE will be returned.
Constraints:
nums.lengthnums[i]
Examples#
No. | nums | Result |
1 | [1, 2, 3] | TRUE |
2 | [4, 2, 7] | FALSE |
3 | [2, 1, 5, 3, 1] | TRUE |
Try it yourself#
Implement your solution in the following playground.
Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.
Hint: Use dynamic programming and see the magic.
Solution#
We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.
Naive approach#
We can solve this problem with the following two steps:
-
First, we calculate the sum of the array. If the sum of the array is odd, there can’t be two subarrays with an equal sum. Therefore, we return FALSE.
-
If the sum is even, we calculate Target Sum Array Sum and find a subarray of the array with a sum equal to Target Sum. The subarray can be found by either including the current element or not including it. To include the current element, we need to subtract it from the Target Sum.
The first step can be calculated easily, and the second can be solved using recursion. In the recursive approach, we calculate the result repeatedly by decreasing the problem set and evaluating the solution at every stage. For example, consider an array [1, 2, 3, 2, 6, 2], that can be partitioned into [1, 2, 3, 2] and [6, 2], with the sum equal to 8.
Let’s implement the algorithm as discussed above:
Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.
Time complexity#
The time complexity of this approach is . In the worst case, for each element in the array, this solution tests two possibilities, whether to include or exclude it.
Space complexity#
Since we can’t have more than recursive calls on the call stack at any time, the space complexity of this approach is .
Optimized solution using dynamic programming#
Now, let’s improve the recursive solution using top-down and bottom-up approaches.
Top-down solution#
The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array.
As the recursive approach shows, the sum 6 + 2 = 8 is computed twice, which takes extra time. We can avoid the repeated work done in the naive approach by storing the result calculated at each step.
We can use a dictionary named Memo that will store two things; the index of the element and the target sum. Using memoization and recursion to go further for any element in the array, we can:
Choose that element, in which case, the Target Sum will be updated as Target Sum
Target Sum Nums [i]. If we ignore the
element and move forward, Target Sum will remain the same. If Target Sum
, then return TRUE. If Target Sum
, then return FALSE.
Let’s implement the algorithm as discussed above:
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Time complexity#
The time complexity for this approach is
Space complexity#
Since we are using a dictionary to store two things, the array index and the target sum, the space complexity of this approach is
Bottom-up solution#
The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. The problem is divided into subproblems, which are dependent on each other. We create a 2-D table of dimensions , where is the size of the array and is the Target Sum calculated as Target Sum = Array Sum, to store the result of subproblems. If we encounter the same sub-problem later, we can return the stored result from the table with a lookup instead of recalculating that subproblem.
We will use the previously computed subproblem’s results in further calculations to fill the table indices by:
-
Place FALSE in the first row of the table and TRUE in the first column of the table.
-
Let’s assume that the means whether the Target Sum can be achieved from the first elements. If we can pick a series of numbers from to whose sum is , then is TRUE. Otherwise, it is FALSE.
The above step can be computed by using the following:
dp[i][j] = dp[i - 1][j - nums[i - 1]] or dp[i - 1][j] -
Return the value of the last index of the table, which denotes whether the array can be partitioned.
-
If we get (TRUE), the array can be partitioned.
-
If we get (FALSE), the array can not be partitioned.
-
The value for can be calculated with the help of and , which are computed earlier. We don’t need to compute them again, which is the advantage of dynamic programming.
Let’s look at the following illustration to get a better understanding of the solution:
1 of 12
2 of 12
3 of 12
4 of 12
5 of 12
6 of 12
7 of 12
8 of 12
9 of 12
10 of 12
11 of 12
12 of 12
Let’s implement the algorithm as discussed above:
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Minimum Number of Refueling Stops
Count Square Submatrices